Sari la conținut

Compoziție (combinatorică)

De la Wikipedia, enciclopedia liberă
Pentru alte sensuri, vedeți Compoziție.

În matematică compoziția unui număr întreg, n, este un mod de a scrie n ca suma unui șir de numere întregi strict pozitive. Două șiruri care diferă în ordinea termenilor definesc compoziții diferite ale sumei lor, dar se consideră că definesc aceeași partiție⁠(d) a acelui număr. Fiecare număr întreg are un număr finit de compoziții distincte. Numerele negative nu au compoziții, dar 0 are o singură compoziție, șirul vid. Fiecare număr întreg pozitiv n are 2n−1 compoziții distincte.

Bijecție între numerele binare de 3 cifre și compozițiile de 4

O compoziție slabă a unui număr întreg n este similară cu o compoziție a lui n, dar permițând termenilor șirului să fie zero: este un mod de a scrie n ca suma unui șir de întregi nenegativi. Ca o consecință, dacă lungimea compozițiilor nu este mărginită, fiecare număr întreg pozitiv admite un număr infinit de compoziții slabe. Adăugarea unui număr de termeni 0 la sfârșitul unei compoziții slabe nu este de obicei considerată a defini o compoziție slabă diferită; cu alte cuvinte, se presupune că compozițiile slabe sunt extinse implicit la nesfârșit prin termeni 0.

Pentru a generaliza în continuare, o compoziție restricționată A a unui număr întreg n, pentru o submulțime A a numerelor întregi (nenegative sau pozitive), este o colecție ordonată de unul sau mai multe elemente din A a căror sumă este n.[1]

Cele 32 de compoziții ale lui 6

1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 2 + 1 + 1 + 1
. . .
1 + 5
6
Cele 11 partiții ale lui 6

1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1
3 + 1 + 1 + 1
. . .
3 + 3
6

Cele 16 compoziții ale lui 5 sunt:

  • 5
  • 4 + 1
  • 3 + 2
  • 3 + 1 + 1
  • 2 + 3
  • 2 + 2 + 1
  • 2 + 1 + 2
  • 2 + 1 + 1 + 1
  • 1 + 4
  • 1 + 3 + 1
  • 1 + 2 + 2
  • 1 + 2 + 1 + 1
  • 1 + 1 + 3
  • 1 + 1 + 2 + 1
  • 1 + 1 + 1 + 2
  • 1 + 1 + 1 + 1 + 1.

A se compara cu cele 7 partiții ale lui 5:

  • 5
  • 4 + 1
  • 3 + 2
  • 3 + 1 + 1
  • 2 + 2 + 1
  • 2 + 1 + 1 + 1
  • 1 + 1 + 1 + 1 + 1.

Este posibil să se pună constrângeri asupra părților compozițiilor. De exemplu, cele cinci compoziții ale lui 5 în termeni diferiți sunt:

  • 5
  • 4 + 1
  • 3 + 2
  • 2 + 3
  • 1 + 4.

A se compara cu cele 3 partiții ale lui 5 în termeni diferiți:

  • 5
  • 4 + 1
  • 3 + 2.

Numărul compozițiilor

[modificare | modificare sursă]
Numărul compozițiilor lui n+1 în k+1 partiții ordonate formează triunghiul lui Pascal
Folosind numerele Fibonacci pentru a număra compozițiile restricționate {1, 2} ale lui n, de exemplu numărul de moduri în care se poate urca o scară de lungimea n, urcând odată una sau două trepte

Convențional, compoziția vidă este socotită ca singura compoziție de 0 și nu există compoziții de numere întregi negative. Există 2n−1 compoziții ale lui n ≥ 1, iată demonstrația:

Plasarea fie a unui semn plus, fie a unei virgule în fiecare dintre cele n−1 casete ale matricei

produce o compoziție unică de n. Invers, fiecare compoziție a lui n determină o atribuire de plusuri și virgule. Deoarece există n−1 opțiuni binare, se obține rezultatul. Același argument arată că numărul de compoziții ale lui n în exact k părți (o k-compoziție) este dat de coeficientul binomial . De reținut că prin însumarea tuturor numerelor posibile de părți, se regăsește valoare de 2n−1 ca număr total de compoziții ale lui n:

Pentru compozițiile slabe, numărul este , deoarece la fiecare k-compoziție a lui n+k corespunde una slabă dintre cele n după regula:

Din această formulă rezultă că numărul de compoziții slabe ale lui n în exact k părți este egal cu numărul de compoziții slabe ale lui k−1 în exact n+1 părți.

Pentru compozițiile restricționate ale lui A, numărul de compoziții ale lui n în exact k părți este dat de coeficientul binomial (sau polinomial) extins , unde parantezele pătrate indică extragerea coeficientului lui din polinomul care îl urmează.[2]

Polinoame omogene

[modificare | modificare sursă]

Dimensiunea spațiului vectorial al polinomului omogen de gradul d în n variabile peste corpul K este numărul de compoziții slabe ale lui d în n părți. De fapt, o bază pentru spațiu este dată de mulțimea de monoame astfel încât . Deoarece exponenții pot fi zero, atunci numărul de astfel de monoame este exact cu numărul de compoziții slabe ale lui d.

  1. ^ Heubach, Silvia; Mansour, Toufik (). „Compositions of n with parts in a set”. Congressus Numerantium. 168: 33–51. CiteSeerX 10.1.1.484.5148Accesibil gratuit. 
  2. ^ en Eger, Steffen (). „Restricted weighted integer compositions and extended binomial coefficients” (PDF). Journal of Integer Sequences. 16. 
  • en Heubach, Silvia; Mansour, Toufik (). Combinatorics of Compositions and Words. Discrete Mathematics and its Applications. Boca Raton, Florida: CRC Press. ISBN 978-1-4200-7267-9. Zbl 1184.68373. 

Legături externe

[modificare | modificare sursă]